package com.qjc.demo.sort.快速排序;

/**
 * 快速排序：采用分治算法，先找到一个基准元素，然后大于该元素的右移，小于该元素的左移，
 * 然后递归排序该元素左边和右边的数组
 * 单边循环：首先选定基准元素baseNum，同时设置一个mark指针指向数组起始位置，接下来从基准元素的下一个位置开始遍历数组，
 * 小于基准元素的话需要把mark指针右移，然后让最新遍历的元素和mark指针所在位置的元素进行交换，继续遍历，最后把baseNum元素和mark所在位置元素交换。
 *
 * @ClassName: Solution
 * @Author: qjc
 * @Date: 2023/9/13 09:35
 */
public class Solution {

    public static void quickSort(int[] arr, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        // 获取基准元素位置
        int baseNumIndex = partition(arr, startIndex, endIndex);
        // 对左边进行排序
        quickSort(arr, startIndex, baseNumIndex - 1);
        // 对右边进行排序
        quickSort(arr, baseNumIndex + 1, endIndex);
    }

    private static int partition(int[] arr, int startIndex, int endIndex) {
        // 取第一个元素为基准元素
        int baseNum = arr[startIndex];
        // mark指针
        int mark = startIndex;
        for (int i = startIndex + 1; i <= endIndex; i++) {
            if (arr[i] < baseNum) {
                // 与基准元素进行比较，如果小于基准元素则指针右移，然后arr[i]与mark所在位置的元素进行交换
                mark++;
                int temp = arr[mark];
                arr[mark] = arr[i];
                arr[i] = temp;
            }
        }
        // 最后基准元素和mark所在位置元素进行交换
        arr[startIndex] = arr[mark];
        arr[mark] = baseNum;

        return mark;
    }

    public static void main(String[] args) {
        int[] arr = {6, 3, 5, 8, 2, 9, 1};
        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i);
        }
    }

}
